/**
 * 
 */
package tree;

import utils.CreateUtils;

/**
 * @author Michael
 *
 */
public class FindTheNthLargestNodeInBST {

	public static int findTheNthLargest(Node<Integer> root, int n, int rank) {
		if (root == null)
			return rank;
		rank = findTheNthLargest(root.right, n, rank);
		++rank;
		if (n == rank) {
			System.out.printf("%d", root.value);
			return rank;
		}

		return findTheNthLargest(root.left, n, rank);
	}

	public static int findTheNthSmallest(Node<Integer> root, int n, int rank) {
		if (root == null)
			return rank;
		rank = findTheNthSmallest(root.left, n, rank) + 1;
		if (n == rank) {
			System.out.printf("%d", root.value);
			//return rank;
		}
		return findTheNthSmallest(root.right, n, rank);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node<Integer> root = CreateUtils.bstWithTenNodes();
		int rank = findTheNthSmallest(root, 2, 0);
		System.out.println();
		System.out.printf("rank: %d", rank);
		//findTheNthLargest(root, 2, 0);
	}

	/**
	 * 
	 */
	public FindTheNthLargestNodeInBST() {
		// TODO Auto-generated constructor stub
	}
}
